package 排序;

public class RadixSort extends Sort<Integer>{

	@Override
	protected void sort() {
		int max = array[0];
		for (int i = 1; i < array.length; i++) {
			if (array[i] > max) max = array[i];
		}
		
		for (int divider = 1; divider <= max; divider *= 10) {
			countingSort(divider);
		}
		
	}
	
	private void countingSort(int divider) {
		int[] counts = new int[10];
		for (int i = 0; i < array.length; i++) {
			counts[array[i] / divider % 10]++;
		}
		for (int i = 1; i < counts.length; i++) {
			counts[i] += counts[i - 1];
		}
		
		Integer[] newArray = new Integer[array.length];
		for (int i = array.length - 1; i >= 0 ; i--) {
			newArray[--counts[array[i] / divider % 10]] = array[i];
		}
		
		for (int i = 0; i < newArray.length; i++) {
			array[i] = newArray[i];
		}
	}

}
